#include <cstdlib>
#include <string>
#include <stack>
#include <iostream>

using namespace std;


class Solution{
private:
	char counter(char a){
		char val;
		switch (a){
		case '(':
			val = ')';
			break;
		case ')':
			val = '(';
			break;
		case '[':
			val = ']';
			break;
		case ']':
			val = '[';
			break;
		case '{':
			val = '}';
			break;
		case '}':
			val = '{';
			break;
		default:
			break;
		}
		return val;
	}
	bool isleft(char a){
		return a == '[' || a == '(' || a == '{';
	}
public:
	bool isValid(string s){
		stack<char> chars;
		for (int i = 0; i < s.length(); ++i){
			if (chars.empty()){
				if (isleft(s[i]))
					chars.push(s[i]);
				else return false;
			}
			else if (!isleft(s[i]) && chars.top() == counter(s[i])){
				chars.pop();
			}
			else if (!isleft(s[i]) && chars.top() != counter(s[i])){
				return false;
			}
			else
				chars.push(s[i]);
		}
		if (chars.empty()) return true;
		else return false;
	}
};



int main(int argc, char** argv){
	cout << Solution().isValid("(){}]") << endl;
	return 0;
}